package com.zry.demo;

public class FirstPosCircle {
    private static class Node {
        String data;
        Node next;
    }

    /**
     * 假定起点到环入口点的距离为 a，p1 和 p2 的相交点M与环入口点的距离为b，环路的周长为L，当 p1 和 p2 第一次相遇的时候，假定 p1 走了 n 步
     * p1走的路径： a+b ＝ n；
     * p2走的路径： a+b+kL = 2n； p2 比 p1 多走了k圈环路，总路程是p1的2倍
     * 根据上述公式可以得到 k*L=a+b=n显然，如果从相遇点M开始，p1 再走 n 步的话，还可以再回到相遇点，同时p2从头开始走的话，经过n步，也会达到相遇点M。
     * 显然在这个步骤当中 p1 和 p2 只有前 a 步走的路径不同，所以当 p1 和 p2 再次重合的时候，必然是在链表的环路入口点上。
     * @param firstHead
     * @return
     */
    private Node firstPointCircle(Node firstHead){
        if (firstHead.next == null || firstHead.next.next == null) {
            return firstHead;
        }
        Node head = firstHead;

        Node slow = firstHead.next;
        Node fast = firstHead.next.next;

        while (fast != null && slow != null) {
            //快指针追上了慢指针，说明是绕了一圈回来了
            if (slow == fast) {
                break;
            } else {
                //遇到null 说明链表不是环
                if (fast.next == null) {
                    break;
                }

                fast = fast.next.next;
                slow = slow.next;
            }
        }

        fast = head;

        while (slow.data != fast.data) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }

    public static void main(String[] args) {
        Node node1 = new Node();
        node1.data = "汪1";

        Node node2 = new Node();
        node2.data = "汪2";

        Node node3 = new Node();
        node3.data = "汪3";

        Node node4 = new Node();
        node4.data = "汪4";

        Node node5 = new Node();
        node5.data = "汪5";

        Node node6 = new Node();
        node6.data = "汪6";

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node4;

        Node firstPointInCircle = new FirstPosCircle().firstPointCircle(node1);
        System.out.println("first point in circle=" + firstPointInCircle.data);
    }
}
